package midsearch;

/**
 * 题目 ：山峰数组顶部
 * 题目详述 ：
 * 符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
 * arr.length >= 3
 * 存在 i（0 < i< arr.length - 1）使得：
 * arr[0] < arr[1] < ... arr[i-1] < arr[i]
 * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
 * 给定由整数组成的山峰数组 arr ，
 * 返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i，即山峰顶部。
 */
public class PeakIndexInMountainArray {
    public int peakIndexInMountainArray(int[] arr) {
        int start = 1;
        int end = arr.length - 2;
        while(start <= end){
            /**
             * 问题在于：
             * middle - 1 和 middle + 1极有可能会超出当前数组num的边界，
             * 若是超出num数组边界的话，就会报IndexOutOfArray错误；
             *
             * 解决方法 ：
             * 即，默认顶峰元素必然是在数组中间，即位于最左边/最右边的数组最大元素，不为顶峰元素；
             * 所以，start == 1 && end == arr.length - 2，只需要二分查找[start，end]中的元素，就能够确定有无顶峰元素
             */
            // middle元素取值范围 ： start <= middle <= end;
            // 默认顶峰元素位于数组中间（并不会去包括数组的最左边/最右边元素）
            int middle = (start + end) / 2;
            // 由于任意两个相邻元素都不相等，即当前遍历的数组元素比前/后一个元素都大的话，就寻找到了山峰数组的顶峰元素
            if(arr[middle] > arr[middle - 1] && arr[middle] > arr[middle + 1]){
                return middle;
            }
            // 即，若是当前遍历的数组元素大于前一个元素，同时小于后一个元素的话，那么所要寻找山峰数组的顶峰元素在后半部分；
            else if (arr[middle] > arr[middle - 1] && arr[middle] < arr[middle + 1]){
                start = middle + 1;
            }
            // 即，若是当前遍历的数组元素小于前一个元素，同时大于后一个元素的话，那么所要寻找山峰数组的顶峰元素在前半部分；
            else if (arr[middle] < arr[middle - 1] && arr[middle] > arr[middle + 1]){
                end = middle - 1;
            }
        }
        // 即，顶峰数组中的顶峰元素，若是在数组的最左边/最右边的话，那么其就不满足顶峰元素的定义，即不存在此顶峰元素；
        return -1;
    }
    /**
     * 分析 ：
     * 时间复杂度 ：由于使用二分查找进行查询，即时间复杂度：O（n）；
     */
}
